package leetcode.code1036;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.TreeSet;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	int START = 0;
	int MAX = (int) 1e6;

	int[] dirction = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
		TreeSet<Integer> rows = new TreeSet<>();
		TreeSet<Integer> cols = new TreeSet<>();
		for (int[] block : blocked) {
			rows.add(block[0]);
			cols.add(block[1]);
		}
		rows.add(source[0]);// 若不是这两货，直接Arrays.sort了
		rows.add(target[0]);
		cols.add(source[1]);
		cols.add(target[1]);
		int last = rows.first();
		int indexr = last == 0 ? 0 : 1;// 第一个数原本是0，则从0开始，如果不是，说明上面存在一行至多行，需要留出空行
		Map<Integer, Integer> hashRows = new HashMap<>();
		hashRows.put(last, indexr);// 别忘了第一个
		Integer[] row = rows.toArray(new Integer[rows.size()]);
		for (int i = 1; i < row.length; i++) {
			int r = row[i];
			indexr += r == last + 1 ? 1 : 2;// ==last + 1，原本两数相邻，不相等空出一个数+2
			hashRows.put(r, indexr);
			last = r;
		}
		if (last != MAX - 1) {
			indexr += 1;// 没到边界至少还有一行
		}
		last = cols.first();
		int indexc = last == 0 ? 0 : 1;// 第一个数原本是0，则从0开始，如果不是，说明上面存在一行至多行，需要留出空行
		Map<Integer, Integer> hashCols = new HashMap<>();
		hashCols.put(last, indexc);// 别忘了第一个
		Integer[] col = cols.toArray(new Integer[cols.size()]);
		for (int i = 1; i < col.length; i++) {
			int c = col[i];
			indexc += c == last + 1 ? 1 : 2;// ==last + 1，原本两数相邻，不相等空出一个数+2
			hashCols.put(c, indexc);
			last = c;
		}
		if (last != MAX - 1) {
			indexc += 1;// 没到边界至少还有一行
		}
		int[][] compress = new int[indexr + 1][indexc + 1];
		for (int[] block : blocked) {
			compress[hashRows.get(block[0])][hashCols.get(block[1])] = 1;
		}
		int sr = hashRows.get(source[0]), sc = hashCols.get(source[1]);
		int tr = hashRows.get(target[0]), tc = hashCols.get(target[1]);
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { sr, sc });
		compress[sr][sc] = 1;
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			for (int i = 0; i < 8; i += 2) {
				int nr = cur[0] + dirction[i];
				int nc = cur[1] + dirction[i + 1];
				if (nr < 0 || nr > indexr || nc < 0 || nc > indexc || compress[nr][nc] == 1) {
					continue;
				}
				if (nr == tr && nc == tc) {
					return true;
				}
				compress[nr][nc] = 1;//走过的不走了
				q.add(new int[] { nr, nc });
			}
		}
		return false;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(false,
				this.isEscapePossible(HelpDebug.str2array1("[[0,1],[1,0]]"), HelpDebug.str2array3("[0,0]"), HelpDebug.str2array3("[0,2]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(true,
				this.isEscapePossible(HelpDebug.str2array1("[]"), HelpDebug.str2array3("[0,0]"), HelpDebug.str2array3("[999999,999999]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
